package com.fw.algorithm.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 选择排序 - 效率大于 冒泡排序
 * 选择一个最小的，去和 其它序列元素进行比较，一轮下来，其它元素谁最小 就能得到。
 * 在执行下一次，找到其它序列元素中第二小，即可。
 *
 */
public class SelectSort {


    public static void main(String[] args) {
        //int[] arr = new int[]{8,7,5,99,88};
        //sortArr(arr);
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数 }
        }
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);
            sortFinalArr(arr);


        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);
    }

    /**
     * 最终版 选择排序
     * @param arr
     */
     public static void sortFinalArr(int [] arr){
         for (int i = 0; i < arr.length - 1; i++) {
             int minVal =  arr[i];
             int minIndexVal = i;
             for (int j = i + 1; j < arr.length; j++) {
                 if (minVal > arr[j]){
                      minVal = arr[j];
                      minIndexVal = j;
                 }
             }
             if (minIndexVal != i){
                 arr[minIndexVal] = arr[i];
                 arr[i] = minVal;
             }

         }

         //System.out.println("排序后。。。");
        // System.out.println(Arrays.toString(arr));
     }


    public static void sortArr(int [] arr){
        /**
         * 开始分析
         * 假设 arr 数组元素中，第一个是最小的，开始比较
         * 8,7,5,99,88   ； minVal = 8;minIndexVal = 0;
         * 第一次轮回  5,7,8,99,88 minVal = 5, minIndexVal = 2;
         * 第二次轮回  5,7,8,99,88 因为取得是  7 跳过索引 0，开始比较，自身最小。形成规则性
         */
        int minVal =  arr[0];
        int minIndexVal = 0;
        for (int i = 0 + 1; i < arr.length; i++) {
            if (minVal > arr[i]){
                // 发现有比它大的。 进行交换
                minVal =   arr[i];
                minIndexVal = i;
            }
        }
        // 交换
        if (minIndexVal != 0){
            arr[minIndexVal] = arr[0];
            arr[0] =  minVal;
        }
        System.out.println("第一次排序后。。。");
        System.out.println(Arrays.toString(arr));



         minVal =  arr[1];
         minIndexVal = 1;
        for (int i = 1 + 1; i < arr.length; i++) {
            if (minVal > arr[i]){
                // 发现有比它大的。 进行交换
                minVal =   arr[i];
                minIndexVal = i;
            }
        }
        // 交换 优化
        if (minIndexVal != 1){
            arr[minIndexVal] = arr[1];
            arr[1] =  minVal;
        }
        System.out.println("第二次排序后。。。");
        System.out.println(Arrays.toString(arr));
    }
}
